//原文链接：https://blog.csdn.net/ITSOK_123/article/details/124073152
//哈希集合解法
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
    	//哈希集合存储已经遍历过的节点
        unordered_set<ListNode*> visited;
        ListNode* cur = head;
        while(cur!=nullptr){
            if(visited.count(cur)==0){
                visited.insert(cur);
            }
            else return cur;
            cur = cur->next;
        }
        return nullptr;
    }
};


//快慢指针解法
  ListNode *detectCycle(ListNode *head) {
        if(head == nullptr || head->next == nullptr){
            return nullptr;
        }
        //分别设置慢指针快指针
        ListNode* sPtr = head;
        ListNode* fPtr = head;
        while(fPtr != nullptr && fPtr->next!=nullptr){
            sPtr = sPtr->next;
            fPtr = fPtr->next->next;
            //若快慢指针相遇则说明有环
            //条件b+d=c=a+b
            while(sPtr == fPtr){
                ListNode* cur1 = fPtr;
                ListNode* cur2 = head;
                //根据数学条件得出相遇点到环入口的距离等于起点到入口的距离
                while(cur1 != cur2){
                    cur1=cur1->next;
                    cur2=cur2->next;
                }
                //再次相遇则为入口
                return cur2;
            }
        }
        return nullptr;
    }
